package com.agile.leetcode.middle.levelOrder;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @Author KD
 * @Date 2021/3/10 15:39
 */
public class LevelOrder {
    public static void main(String[] args) {
        TreeNode treeNode7 = new TreeNode(7);
        TreeNode treeNode15 = new TreeNode(15);
        TreeNode treeNode20 = new TreeNode(20);
        treeNode20.left = treeNode15;
        treeNode20.right = treeNode7;
        TreeNode treeNode9 = new TreeNode(9);
        TreeNode treeNode3 = new TreeNode(3);
        treeNode3.left = treeNode9;
        treeNode3.right = treeNode20;
        LevelOrder levelOrder = new LevelOrder();
        List<List<Integer>> lists = levelOrder.levelOrder(treeNode3);
        System.out.println(lists);

        TreeNode treeNode4 = new TreeNode(4);
        TreeNode treeNode5 = new TreeNode(5);
        TreeNode treeNode2 = new TreeNode(2);
        TreeNode treeNode33 = new TreeNode(3);
        TreeNode treeNode1 = new TreeNode(1);
        treeNode2.left = treeNode4;
        treeNode33.right = treeNode5;
        treeNode1.left = treeNode2;
        treeNode1.right = treeNode33;
        List<List<Integer>> lists1 = levelOrder.levelOrder(treeNode1);
        System.out.println(lists1);
    }

    /**
     * 层次遍历
     *
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        // 创建返回集合
        List<List<Integer>> list = new ArrayList<>(10);
        if (root == null) return list;
        // 创建队列
        Deque<TreeNode> deque = new LinkedList<>();
        // 定义计数器 1 从左往右，2从右往左
        boolean isLeft = true;
        deque.add(root);
        // 死循环
        while (deque.size() != 0) {
            List<Integer> list1 = new ArrayList<>(10);
            // 拿到长度
            int len = deque.size();
            for (int j = 0; j < len; j++) {
                //
                if (isLeft) {
                    // 循环
                    TreeNode node = deque.pollFirst();
                    // 拿到值
                    int val = node.val;
                    // 加入集合
                    list1.add(val);
                    // 奇数
                    if (node.left != null) {
                        deque.addLast(node.left);
                    }
                    if (node.right != null) {
                        deque.addLast(node.right);
                    }
                } else {
                    // 循环
                    TreeNode node = deque.pollLast();
                    // 拿到值
                    int val = node.val;
                    // 加入集合
                    list1.add(val);
                    // 偶数
                    if (node.right != null) {
                        deque.addFirst(node.right);
                    }
                    if (node.left != null) {
                        deque.addFirst(node.left);
                    }
                }
            }
            // 升级
            isLeft = !isLeft;
            // 加入集合
            list.add(list1);
        }
        return list;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(int val) {
        this.val = val;
    }
}
